/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2023-01-09
 * Time:19:11
 */
class ListNode{
    int val;
    ListNode next;
    public ListNode(int val){
        this.val=val;
    }
}
class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                fast=head;
                while(fast!=slow){
                    fast=fast.next;
                    slow=slow.next;
                }
                return fast;
            }
        }
        return null;
    }
    public boolean hasCycle(ListNode head) {
        if(head==null){
            return false;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            if(fast.next==slow||fast.next.next==slow){
                return true;
            }
            fast=fast.next.next;
            slow=slow.next;
        }
        return false;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode list1=headA;
        ListNode list2=headB;
        int size1=0;
        int size2=0;
        while(list1!=null){
            size1++;
            list1=list1.next;
        }
        while(list2!=null){
            size2++;
            list2=list2.next;
        }
        list1=headA;
        list2=headB;
        if(size1>size2){
            for (int i = 0; i < size1-size2; i++) {
                list1=list1.next;
            }
        }else{
            for (int i = 0; i < size2-size1; i++) {
                list2=list2.next;
            }
        }
        while(list1!=null){
            if(list1==list2){
                return list1;
            }
            list1=list1.next;
            list2=list2.next;
        }
        return null;
    }
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if(A==null||A.next==null){
            return true;
        }
        ListNode fast=A;
        ListNode slow=A;
        while(fast.next!=null&&fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //反转后半部分链表
        ListNode cur=slow.next;
        slow.next=null;
        ListNode curnext=cur.next;
        cur.next=null;
        while(curnext!=null){
            ListNode pre=curnext.next;
            curnext.next=cur;
            cur=curnext;
            curnext=pre;
        }
        //循环判断
        while(cur!=null){
            if(cur.val!=A.val){
                return false;
            }
            cur=cur.next;
            A=A.next;
        }
        return true;
    }
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        if(pHead==null){
            return pHead;
        }
        ListNode listpre=new ListNode(-1);
        ListNode listcur=new ListNode(-1);
        ListNode pre=listpre;
        ListNode cur=listcur;
        while(pHead!=null){
            if(pHead.val<x){
                pre.next=pHead;
                pre=pre.next;
            }else{
                cur.next=pHead;
                cur=cur.next;
            }
            pHead=pHead.next;
        }
        if(listpre.next==null){
            return listcur.next;
        }
        pre.next=listcur.next;
        if(cur!=null){
            cur.next=null;
        }
        return listpre.next;
    }
}
public class Test {
}
